#ifndef GRAPH_H
#define GRAPH_H

// A directed graph.  Vertices and edges both can have attributes
// Doesn't implement everything you could with boost::graph,
// such as deleting vertices and edges.

#include <vector>
#include <iostream>
#include "Iterators.h"
#include "Parser_Special.h"

template <class EP>
class Graph_Edge {
public:
    int tail, head;
    EP property;

    Graph_Edge(int p_tail, int p_head, const EP& p_property)
        : tail(p_tail), head(p_head), property(p_property) {
    }
};

template <class VP, class EP, class VN>
class Graph_Vertex {
public:
    VP property;
    VN name;
    std::vector<Graph_Edge<EP>*> neighbors;

    Graph_Vertex(const VP& p_property, int expected_valence, const VN& p_name)
        : property(p_property), name(p_name) {
        if (expected_valence != 0)
            neighbors.reserve(expected_valence);
    }
};

template <class VP, class EP, class VN>
class Graph {
public:
    Graph(int expected_n_vertices,
          int expected_n_edges,
          int expected_valence,
          bool directed) {
        this->is_directed = directed;
        this->expected_valence = expected_valence;
        if (expected_n_vertices > 0)
            vertices.reserve(expected_n_vertices);
        if (expected_n_edges > 0)
            edges.reserve(expected_n_edges);
    }

    void add_vertex(const VN& name, const VP& property)  {
        Graph_Vertex<VP,EP,VN> *v = new Graph_Vertex<VP,EP,VN>(property, expected_valence, name);
        vertices.push_back(v);
        vertex_index_by_name[name] = vertices.size() - 1;
    }

    void add_edge(const VN tail_name,
                  const VN head_name,
                  const EP& property) {
        int tail = vertex_index_by_name[tail_name];
        int head = vertex_index_by_name[head_name];
        edges.push_back(new Graph_Edge<EP>(tail, head, property));
        vertices[tail]->neighbors.push_back(edges[edges.size()-1]);
        if (!is_directed) {
            edges.push_back(new Graph_Edge<EP>(head, tail, property));
            vertices[head]->neighbors.push_back(edges[edges.size()-1]);
        }
    }

    Iterator<Graph_Vertex<VP,EP,VN>*> *new_vertex_iterator() {
        return new Iterator_Vector<Graph_Vertex<VP,EP,VN>*>(vertices.begin(),
                                                            vertices.end());
    }

    Iterator<Graph_Edge<EP>*>      *new_edge_iterator() {
        return new Iterator_Vector<Graph_Edge<EP>*>(edges.begin(),
                                                    edges.end());
    }

    Iterator<Graph_Edge<EP>*>      *new_vertex_adjacency_iterator(int vertex) {
        return new Iterator_Vector<Graph_Edge<EP>*>
            (vertices[vertex]->neighbors.begin(),
             vertices[vertex]->neighbors.end());
    }

    std::ostream& print(std::ostream& os) {
        int n = vertices.size();
        for (int i = 0; i < n; i++) {
            Graph_Vertex<VP,EP,VN> *v = vertices[i];
            os << v->name << " [" << v->property << "]\n";
        }

        n = edges.size();
        for (int i = 0; i < n; i++) {
            Graph_Edge<EP> *e = edges[i];
            VN tail_name = vertices[e->tail]->name;
            VN head_name = vertices[e->head]->name;
            os << tail_name << " > " << head_name << " [" << e->property << "]\n";
        }
        return os;
    }

    void read(Parser_Special& p) {
        std::string text_line;
        while (!p.eof()) {
            p.next_line();
            /* if (p.eof()) */
            /*     break; */

            VN vertex_name;
            VN tail_name;
            VN head_name;
            VP vertex_property;
            EP edge_property;

            if (match_vertex(p, vertex_name, vertex_property)) {
                add_vertex(vertex_name, vertex_property);
            }
            else if (match_edge(p, tail_name, head_name, edge_property)) {
                add_edge(tail_name, head_name, edge_property);
            }
            else {
                throw std::string("malformed data line: " + text_line);
            }
        }
    }

private:
    bool match_vertex(Parser_Special& parser, VN& vn, VP& vp) {
        // Cases:
        // a: 10              lone vertex (OK)
        // b: 10 > 20         edge        (BAD)
        // c: 10 [1 2 3 4 5]  vertex with property (OK)
        int m = 0;

        m += parser.match(vn);
        if (m != 1) {
            parser.backup(1); // weird invalid non-vertex, non-edge line
            return false;
        }

        if (parser.line_done()) { // case a
            return true;
        }

        m += parser.match_char("[");
        if (m == 2) {// case c
//            parser.backup(m); // undo bracket
            return parser.match(vp) != 0;
        }

        else { // case b
            parser.backup(m + 1); // undo first vertex name
            return false;
        }
    }

    bool match_edge(Parser_Special& parser,
                    VN& src,
                    VN& dst,
                    EP& ep) {
        // Cases:
        // one > two  (OK)
        // one > two [123] (OK)
        // one (BAD)
        // one [abc] (BAD)

        int m = 0;

        m  = parser.match (src);
        m += parser.match_char(">");
        m += parser.match (dst);

        if (m == 3) {
            if (parser.match_char("[")) {
                if (parser.match(ep) != 0) {
                    return true;
                }
                return false;
            }
        }

        parser.backup(m);
        return false;
    }

private:
    bool is_directed;
    int expected_valence;
    std::vector<Graph_Vertex<VP,EP,VN>*> vertices;
    std::vector<Graph_Edge<EP>*> edges;
    std::unordered_map<VN, int> vertex_index_by_name;
};

template < typename VP, typename EP, typename VN >
std::ostream& operator<<( std::ostream& os,
                          Graph<VP,EP,VN>& g ) {
    return g.print(os);
}

#endif
